﻿// 1368. 使网格图至少有一条有效路径的最小代价.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>

using namespace std;
/*
https://leetcode.cn/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/

给你一个 m x n 的网格图 grid 。 grid 中每个格子都有一个数字，对应着从该格子出发下一步走的方向。 grid[i][j] 中的数字可能为以下几种情况：

1 ，下一步往右走，也就是你会从 grid[i][j] 走到 grid[i][j + 1]
2 ，下一步往左走，也就是你会从 grid[i][j] 走到 grid[i][j - 1]
3 ，下一步往下走，也就是你会从 grid[i][j] 走到 grid[i + 1][j]
4 ，下一步往上走，也就是你会从 grid[i][j] 走到 grid[i - 1][j]
注意网格图中可能会有 无效数字 ，因为它们可能指向 grid 以外的区域。

一开始，你会从最左上角的格子 (0,0) 出发。我们定义一条 有效路径 为从格子 (0,0) 出发，每一步都顺着数字对应方向走，最终在最右下角的格子 (m - 1, n - 1) 结束的路径。
有效路径 不需要是最短路径 。

你可以花费 cost = 1 的代价修改一个格子中的数字，但每个格子中的数字 只能修改一次 。

请你返回让网格图至少有一条有效路径的最小代价。



示例 1：



输入：grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
输出：3
解释：你将从点 (0, 0) 出发。
到达 (3, 3) 的路径为： (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) 花费代价 cost = 1 使方向向下 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) 
花费代价 cost = 1 使方向向下 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) 花费代价 cost = 1 使方向向下 --> (3, 3)
总花费为 cost = 3.
示例 2：



输入：grid = [[1,1,3],[3,2,2],[1,1,4]]
输出：0
解释：不修改任何数字你就可以从 (0, 0) 到达 (2, 2) 。
示例 3：



输入：grid = [[1,2],[4,3]]
输出：1
示例 4：

输入：grid = [[2,2,2],[2,2,2]]
输出：3
示例 5：

输入：grid = [[4]]
输出：0


提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
*/


const int N = 10500, M = 40500;

class Solution {
private:
    int h[N], e[M], ne[M],w[M], idx;
    int dist[N];
    int st[N];

    int dijkstra(const vector<vector<int>>& grid)
    {
        memset(dist, 0x3f, sizeof dist);
        memset(st, 0, sizeof st);
        dist[0] = 0;
        priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
        heap.push({ 0, 0 });      // first存储距离，second存储节点编号

        while (heap.size())
        {
            auto t = heap.top();
            heap.pop();

            int ver = t.second, distance = t.first;

            if (st[ver]) continue;
            st[ver] = true;

            for (int i = h[ver]; i != -1; i = ne[i])
            {
                int j = e[i];
                if (dist[j] > distance + w[i])
                {
                    dist[j] = distance + w[i];
                    heap.push({ dist[j], j });
                }
            }
        }

        int m = grid.size();
        int n = grid[0].size();

        if (dist[(m-1)*101+n-1] == 0x3f3f3f3f) return -1;
        return dist[(m - 1) * 101 + n - 1];
    }

    

    void add(int a, int b, int c) {
        e[idx] = b, w[idx] = c, ne[idx]=h[a], h[a] = idx++;
    }

    void init(const vector<vector<int>>& grid) {
        memset(h, -1, sizeof h); idx = 0;
        unordered_set<int> ss;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                int v = grid[i][j];
                int hashV = i * 1010 + j * 10 + v;
                ss.insert(hashV);

                int curr = i * 101 + j;
                int next = 0;
                if (v == 1 && j+1< grid[0].size()) {
                    next = i * 101 + j + 1;
                    add(curr, next, 0);
                }
                else if (v == 2 && j-1>=0) {
                    next = i * 101 + j - 1;
                    add(curr, next, 0);
                }
                else if (v == 3 && i+1 < grid.size()) {
                    next = (i + 1)* 101 + j ;
                    add(curr, next, 0);
                }
                else if (v == 4 && i -1 >=0) {
                    next = (i - 1) * 101 + j;
                    add(curr, next, 0);
                }
            }
        }

        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                for (int v = 1; v <= 4; v++) {
                    int hashV = i * 1010 + j * 10 + v;
                    if (ss.count(hashV) != 0) continue;

                    int curr = i * 101 + j;
                    int next = 0;
                    if (v == 1 && j + 1 < grid[0].size()) {
                        next = i * 101 + j + 1;
                        add(curr, next, 1);
                    }
                    else if (v == 2 && j - 1 >= 0) {
                        next = i * 101 + j - 1;
                        add(curr, next, 1);
                    }
                    else if (v == 3 && i + 1 < grid.size()) {
                        next = (i + 1) * 101 + j;
                        add(curr, next, 1);
                    }
                    else if (v == 4 && i - 1 >= 0) {
                        next = (i - 1) * 101 + j;
                        add(curr, next, 1);
                    }
                }
            }
        }
    }
public:
    int minCost(vector<vector<int>>& grid) {
        init(grid);

        return dijkstra(grid);
    }
};


int main()
{
    Solution s;
    vector<vector<int>> v{
        {2,2,2},{2,2,2}
    };
    cout << s.minCost(v) << endl;
} 